//给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。 
//
// 
// 例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。 
// 
//
// 对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。 
//
// 返回这些数字之和。题目数据保证答案是一个 32 位 整数。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [1,0,1,0,1,0,1]
//输出：22
//解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
// 
//
// 示例 2： 
//
// 
//输入：root = [0]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 树中的节点数在 [1, 1000] 范围内 
// Node.val 仅为 0 或 1 
// 
// Related Topics 树 深度优先搜索 二叉树 👍 156 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;

public class _1022_SumOfRootToLeafBinaryNumbers {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Solution solution = new _1022_SumOfRootToLeafBinaryNumbers().new Solution();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(0);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(1);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(1);

        System.out.println(solution.sumRootToLeaf(root));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public int sumRootToLeaf(TreeNode root) {
            int res = 0;

            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode cur = root;
            int val = 0;
            TreeNode pre = null;
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    val = (val << 1) | cur.val;
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.peek();
                if (cur.right == null || cur.right == pre) {
                    if (cur.left == null && cur.right == null) {
                        res += val;
                    }
                    val >>= 1;
                    stack.pop();
                    pre = cur;
                    cur = null;
                } else {
                    cur = cur.right;
                }
            }

            return res;

//            Deque<TreeNode> stack = new ArrayDeque<>();
//            TreeNode cur = root;
//            while (!stack.isEmpty() || cur != null) {
//                while (cur != null) {
//                    stack.push(cur);
//                    cur = cur.left;
//                }
//                cur = stack.pop();
//                System.out.print(cur.val + " ");
//                cur = cur.right;
//            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}